# !/usr/bin/python
# -*- coding: utf-8 -*-
'''
@File    :   53_最大子序和.py
@Time    :   2021/11/04 16:23:04
@Author  :   Qingxiang Zhang
@Version :   1.0
@Contact :   344285081@qq.com
@Desc    :   分治算法
@Software:    Vscode
'''
"""* 题目描述
难度：简单
  给定一个整数数组 `nums` ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
  示例:
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [0]
输出：0
示例 4：
输入：nums = [-1]
输出：-1
示例 5：
输入：nums = [-100000]
输出：-100000
提示:
1 <= nums.length <= 105
-104 <= nums[i] <= 104

* 解题思路
  * 确定切分的终止条件
    直到所有的子问题都是长度为 1 的数组，停止切分。
  * 准备数据，将大问题切分为小问题
    递归地将原数组二分为左区间与右区间，直到最终的数组只剩下一个元素，将其返回
  * 处理子问题得到子结果，并合并
    - 将数组切分为左右区间
      - 对与左区间：从右到左计算左边的最大子序和
      - 对与右区间：从左到右计算右边的最大子序和
    - 由于左右区间计算累加和的方向不一致，因此，左右区间直接合并相加之后就是整个区间的和
    - 最终返回左区间的元素、右区间的元素、以及整个区间(相对子问题)和的最大值
"""

class Solution:
    def maxSubArray(self, nums) -> int:
        # 确立分割条件
        n = len(nums)
        if n ==1:
            return nums[0]
        # 分割问题
        left = self.maxSubArray(nums[:len(nums)//2])
        rigth = self.maxSubArray(nums[len(nums)//2:])
        # 处理小的问题得到结果
        #　从右到左计算左边的最大子序和
        max_l = nums[len(nums)//2-1]
        temp = 0
        for i in range(len(nums)//2-1,-1,-1):
            temp += nums[i] 
            max_l = max(temp,max_l)
        # 从左到右计算右边的最大子序和
        max_r = nums[len(nums)//2]
        temp=0
        for i in range(len(nums)//2,len(nums)):
            temp += nums[i]
            max_r = max(temp,max_r)
        # 【对子结果进行合并 得到最终结果】
        # 返回三个中的最大值
        return max(left,rigth,max_r+max_l)
    
# nums = [-2,1,-3,4,-1,2,1,-5,4]
    def maxSubArray(self, nums: list[int])->int:
      maxAns = nums[0]
      ans = 0
      for num in nums:
        ans = max(ans + num, num)
        maxAns = max(maxAns, ans)
      return maxAns
